package leetcode.code0753;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

import leetcode.IDebug;

public class Solution4 implements IDebug {

	int limit;
	int k;
	int len;
	char[] ans;

	public String crackSafe(int n, int k) {
		this.k = k;
		limit = (int) Math.pow(10, n);
		len = (int) Math.pow(k, n) + n - 1;
		ans = new char[len];
		LinkedList<Integer> seen = new LinkedList<Integer>();
		int p = 0;
		for (int i = 0; i < n; i++) {
			ans[p++] = '0';
		}
		seen.add(0);
		dfs(0, p, seen);
		String space = "";
		for(int num : seen) {
			System.out.println(space+String.format("%0"+n+"d", num));
			space +=" ";
		}
		return new String(ans);
	}

	public boolean dfs(int node, int p, LinkedList<Integer> seen) {
		if (p == len) {
			return true;
		}
		node *= 10;
		node %= limit;
		for (int x = 0; x < k; ++x) {
			int next = node + x;
			if (!seen.contains(next)) {
				seen.add(next);
				ans[p] = (char) (x + '0');
				if (dfs(next, p + 1, seen))
					return true;
				seen.remove(seen.indexOf(next));
			}
		}
		return false;
	}

	@Override
	public void debug4() {
//		System.out.println(this.crackSafe(3, 4));
		System.out.println(this.crackSafe(3, 3));
//		System.out.println(this.crackSafe(1, 2));
//		System.out.println(this.crackSafe(3, 3));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		StringBuffer sb = new StringBuffer();
		Deque<Integer> queue = new LinkedList<>();
		queue.add(1);
		System.out.println("00222121112201202101102001000".length());
	}

}
